require("token")
---------------------------------------------------------------------------
local priority = {
    ["/"] = 0,
    ["*"] = 0,
    ["%"] = 0,
    
    ["+"] = 1,
    ["-"] = 1,
    
    ["<<"] = 2,
    [">>"] = 2,
    
    [">" ] = 3,
    ["<" ] = 3,
    ["=<"] = 3,
    ["<="] = 3,
    [">="] = 3,
    ["=>"] = 3,
    
    ["=="] = 4,
    ["!="] = 4,
    
    ["&"] = 5,
    
    ["^"] = 6,
    ["|"] = 7,
    ["&&"] = 8,
    ["||"] = 9,
    ["?:"] = 10,
    ["="] = 11,
}

unary_operator = {
['+'] = 1,
['-'] = 1,
['~'] = 1,
['!'] = 1,
}

--Binary expression
--tokens = cast(Token,nil)
function unary_expression(tokens,pos)
    local str,pos2 = tokens:next(pos);
    local str2,pos3 = tokens:next(pos2);
    local tree;
    if(str=='+' and str2=='+')then
        tree,pos = cast_expression(tokens,pos3);
        tree = {value= tree,inc='+'};
    elseif(str=='-' and str2=='-')then
        tree,pos = cast_expression(tokens,pos3);
        tree = {value= tree,inc='-'};
    elseif(unary_operator[str])then
        tree,pos = cast_expression(tokens,pos2);
        tree = {uopr = str,value = tree};
    elseif(str=='(')then
        tree,pos = expression(tokens,pos2,')');
        tree.bracket = 1;
    else
        tree,pos = getVal(tokens,pos);
        str2,pos2 = tokens:next(pos);
        if(str2=='(')then
            --函数调用
            local callTree = {type = 'call'};
            callTree.id = tree;
            local argTree = callTree;
            pos = pos2;
            while(true)do
                tree,pos = expression(tokens,pos,{',',')'});
                if(tree==nil)then
                    --可能是 call([void]) 的形式
                    pos = pos + 1;
                    break;
                end
                local str,npos = tokens:next(pos-1);
                pos = npos;
                argTree.value = tree;
                if(str==')')then
                    pos = npos;
                    break;
                end
                argTree.next = {};
                argTree = argTree.next;
            end
            tree = callTree
        end
        --后缀自加
        str,pos2 = tokens:next(pos);
        str2,pos3 = tokens:next(pos2);
        local op,pos4 = tokens:next(pos3);

        if(priority[op] or op==',' or op==';' or op==')')then
            if((str=='-' or str=='+') and str2==str)then
                tree = {postfix_inc = str,value = tree};
                pos = pos3;
            end
        end
    end
    return tree,pos;
end

function cast_expression(tokens,pos)
    local curTree = {};
    local tree,npos = iscast(tokens,pos);
    local baseTree;
    if(tree)then
        baseTree = tree;
    else
        npos = pos;
    end
    tree,npos = unary_expression(tokens,npos);
    if(baseTree==nil)then
        return tree,npos;
    else
        baseTree.value = tree;
    end
    return baseTree,npos;
end

function isnumber(tokens,pos)
    local str,npos = tokens:next(pos);
    local base;
    if(str:find('[%d]+$'))then
        --十六进制
        local str2,npos2 = tokens:next(npos);
        base = str;
        if(str2=='.')then
            --小数点
            str,npos = tokens:next(npos2);
            if(str=='f' or str:find('([%d]+f?)$'))then
                base = base .. str2 .. str;
            else
                tokens:Seterr('错误小数点表示');
            end
        end
        pos = npos;
    elseif(str:find('0[xX][%da-fA-F]+$') or str:find('0b[10]+$'))then
        --十六进制
        base = str;
        pos = npos;
    end
    return base,pos;
end

function isidentifier(tokens,pos)
    local str,npos = tokens:next(pos);
    local base = {};
    local tree = base;
    while(true)do
        --标识符
        if(str:find('[%u%l_$][%w_$]*'))then
            local str2,npos2 = tokens:next(npos);
            tree.id = str;
            if(str2~='.')then
                pos = npos;
                break;
            end
            tree.member = {};
            tree = tree.member;
            str,npos = tokens:next(npos2);
        else
            return nil;
        end
    end
    return base,pos;
end

function iscast(tokens,pos)
    local str,npos = tokens:next(pos);
    if(str~='(')then return nil; end;
    local tree,npos2 = isidentifier(tokens,npos);
    if(tree)then
        str,npos = tokens:next(npos2);
        if(str==')')then
            tree.type = 'cast';
            return tree,npos;
        end
    end
    return nil;
end

function getVal(tokens,pos)
    local typ = 'id';
    local v,npos = isidentifier(tokens,pos);
    if(v)then return v,npos,typ; end;
    typ = 'number';
    local v,npos = isnumber(tokens,pos);
    if(v)then return v,npos,typ; end;
end

local function proc(tokens,pos,end_token)
    if(end_token==nil)then end_token = ';' end;
    local end_tokenTable = {};
    if(type(end_token)=='table')then
        for k,v in ipairs(end_token)do
            end_tokenTable[v] = true;
        end
    end
    local stack = {};
    local operstack = {};
    local function push_tree(op)
        local op2 = stack[#stack];
        local op1 = stack[#stack-1];
        local ret = {};
        ret.opr = op;
        ret.left = op1;
        ret.right = op2;
        ret.type = 'binop';
        stack[#stack] = nil;
        stack[#stack] = ret;
    end

    --操作数压栈
    local function push_op(var)
        table.insert(stack,var);
    end

    --操作符压栈
    local function push_opr(opr)
        table.insert(operstack,opr);
    end

    while(true)do
        local c;
        local next_pos;
        c,next_pos = tokens:next(pos);
        if(c==end_token or end_tokenTable[c])then
            break;
        end
        -- if(c=='(')then
        --     --(优先级
        --     push_opr(c);
        --     pos = next_pos;
        -- else
            --获得一元表达式
            local var;
            --var,next_pos = unary_expression(tokens,pos);
            var,next_pos = cast_expression(tokens,pos);
            push_op(var);
            local function getopr(tokens,pos)
                local opr,npos = tokens:next(pos);
                local opr2,npos2 = tokens:next(npos);
                if(priority[opr..opr2])then
                    return opr..opr2,npos2;
                end
                return opr,npos;
            end
            --操作符
            local opr,next_pos = getopr(tokens,next_pos);--tokens:next(next_pos);
            if(opr==end_token or end_tokenTable[opr])then
                pos = next_pos;
                break;
            end
            
            --运算符
            if(priority[opr]==nil)then
                tokens:Seterr();
                --错误,非操作符
            end
            push_opr(opr);
            if(#operstack>=2)then
                local top = #operstack;
                local opr2 = operstack[top]
                local opr1 = operstack[top-1];
                --优先级小于或等于
                --可能会有 '('  ')'
                if(priority[opr2] and priority[opr1] and priority[opr2]>=priority[opr1])then
                    push_tree(opr1);
                    table.remove(operstack,1);
                end
            end

            pos = next_pos;
        --end
    end

    while(#operstack>0)do
        push_tree(operstack[#operstack]);
        operstack[#operstack] = nil;
    end
    return stack[1],pos;
end

function expression(...)
    return proc(...);
end

--逆波兰表达式
function ToRPN(tree,list)
    if(list==nil)then list = {}; end;
    if(tree==nil)then return list; end;
    if(type(tree)~='table')then 
        table.insert(list,tree); 
        return list; 
    elseif(tree.uopr)then
        table.insert(list,tree.uopr);
        table.insert(list,'[');
        ToRPN(tree.value,list);
        table.insert(list,']');
        return list;
    end;
    if(tree.bracket)then
        table.insert(list,'(')
    end
    ToRPN(tree.left,list);
    ToRPN(tree.right,list);
    table.insert(list,tree.opr);
    if(tree.bracket)then
        table.insert(list,')')
    end
    return list;
end

if(false)then
local tokens = Token.init([[
    30 + ((40 + 80) + 50) * 60 ;
]]);
local tree = proc(tokens,1);
local v = ToRPN(tree);
for k,v in ipairs(v)do io.stdout:write(v..' '); end;

local tokens = Token.init([[
    max(++10++,20) + 50 * 60 ;
]]);
local v= expression(tokens,1);

local v = ToRPN(v);
for k,v in ipairs(v)do io.stdout:write(v..' '); end;
end
----------------------------------------------------------------------------
--语句
statementList = {};

statementList['if'] = function(tokens,pos)
    local str,npos = tokens:next(pos);
    local str2,npos2 = tokens:next(npos);
    if(str=='if' and str2=='(')then
        local tree,npos3 = expression(tokens,npos2,')');
        str,npos = tokens:next(npos3-1);
        if(str==')')then
            local ifTree = {type='ifstmt',cond = tree};
            local tree,npos = statement(tokens,npos);
            ifTree.stmt = tree;
            return ifTree,npos;
        end
    end
end

statementList['{'] = function(tokens,pos)
    local str,npos = tokens:next(pos);
    local cmstmt = {type='cmstmt',list = {}};
    if(str=='{')then
        pos = npos;
        while(true)do
            str,npos = tokens:next(pos);
            if(str=='}')then
                pos = npos;
                break;
            end
            --单条语句
            local tree,npos = statement(tokens,pos);
            table.insert(cmstmt.list,tree);
            pos = npos;
        end
    end
    return cmstmt,pos;
end

statementList['while'] = function(tokens,pos)
    local str,npos = tokens:next(pos);
    local str2,npos2 = tokens:next(npos);
    if(str=='while' and str2=='(')then
        local tree,npos3 = expression(tokens,npos2,')');
        str,npos = tokens:next(npos3-1);
        if(str==')')then
            local Tree = {type='whilestmt',cond = tree};
            local tree,npos = statement(tokens,npos);
            Tree.stmt = tree;
            return Tree,npos;
        end
    end
end

statementList['for'] = function(tokens,pos)
    local str,npos = tokens:next(pos);
    local str2,npos2 = tokens:next(npos);
    if(str=='for' and str2=='(')then
        local init_tree,npos3 = expression(tokens,npos2,';'); if(init_tree==nil)then npos3 = npos3 + 1; end
        local cond_tree,npos4 = expression(tokens,npos3,';'); if(cond_tree==nil)then npos4 = npos4 + 1; end
        local stmt_tree,npos5 = expression(tokens,npos4,')'); if(stmt_tree==nil)then npos5 = npos5 + 1; end
        str,npos = tokens:next(npos5-1);
        if(str==')')then
            local Tree = {type='forstmt',init=init_tree,cond = tree,next=stmt_tree,};
            local tree,npos = statement(tokens,npos);
            Tree.stmt = tree;
            return Tree,npos;
        end
    end
end

statementList['return'] = function(tokens,pos)
    local str,npos = tokens:next(pos);
    if(str=='return')then
        local tree,pos = expression(tokens,npos);
        local stmt = {type='retstmt',value = tree};
        return stmt,pos;
    end
end

statementList['goto'] = function(tokens,pos)
    local str,npos = tokens:next(pos);
    if(str=='goto')then
        --goto <id>;
        str,pos = tokens:next(npos);
        if(str:find('[%l%u$_][%w_$]*'))then
            local nstr,npos = tokens:next(pos);
            if(nstr==';')then
                local stmt = {type='gotostmt',id=str};
                return stmt,npos;
            end
        end
        tokens:Seterr('错误的goto表达式: goto <id>;');
    end
end

statementList['do'] = function(tokens,pos)
    local str,npos = tokens:next(pos);
    if(str=='do')then
        local stmt,pos = statement(tokens,npos);
        local str,npos = tokens:next(pos);
        local str2,npos2 = tokens:next(npos);
        if(str=='while' and str2=='(')then
            local tree,npos = expression(tokens,npos2,')');
            str,npos = tokens:next(npos-1);
            str2,npos2 = tokens:next(npos);
            if(str==')' and str2==';')then
                local dostmt = {type='dostmt',cond = tree,stmt=stmt};
                return dostmt,npos2;
            end
        end
        tokens:Seterr('错误的表达式,应该修正为:do <stmt> while(<exp>);')
    end
end

function statement(tokens,pos)
    local str,npos = tokens:next(pos);
    if(str==';')then
        return {type='nullstmt'},npos;
    end
    if(statementList[str])then
        return statementList[str](tokens,pos);
    else
        return expression(tokens,pos);
    end
end
--测试
local tokens = Token.init([[
{
    do x =20; while(x++);
        for(y=0;x<20;x++){
            if(x==0){
                ;
                ;
                ;
                x = 20*40+50/2;
                x = 200/20;
                x = 10+40;
            }
        }
    return 20*40;
}
]]);
local v = statement(tokens,1);
print(v);
----------------------------------------------------------------------------
